package leetcode.每日一题;

import org.junit.Test;

import java.util.HashSet;
import java.util.PriorityQueue;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/9 9:44
 * @description :https://leetcode-cn.com/problems/ugly-number-ii/
 */
public class 丑数II {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.nthUglyNumber(10));
    }

    //动态规划
    /*
    class Solution {
        public int nthUglyNumber(int n) {
            int[] dp = new int[n + 1];
            dp[1] = 1;
            int dp2 = 1, dp3 = 1, dp5 = 1;
            for (int i = 2; i <= n; i++) {
                int num2 = dp[dp2] * 2;
                int num3 = dp[dp3] * 3;
                int num5 = dp[dp5] * 5;
                dp[i] = Math.min(num2, Math.min(num3, num5));
                if (dp[i] == num2) dp2++;
                if (dp[i] == num3) dp3++;
                if (dp[i] == num5) dp5++;
            }
            return dp[n];
        }
    }
     */

    class Solution {
        public int nthUglyNumber(int n) {
            PriorityQueue<Long> queue = new PriorityQueue<>();
            HashSet<Long> set = new HashSet<>();
            queue.offer(1L);
            int[] factors = {2, 3, 5};
            long cur = 1;
            for (int i = 1; i <= n; i++) {
                cur = queue.poll();
                for (int factor : factors) {
                    if (set.add(cur * factor))
                        queue.offer(cur * factor);
                }
            }
            return (int) cur;
        }
    }
}
